翻訳と辞書 Words near each other ・ Mats Rondin ・ Mats Rosseli Olsen ・ Mats Rubarth ・ Mats Rudal ・ Mats Rådberg ・ Mats Scheidegger ・ Mats Seuntjens ・ Mats Solheim ・ Mats Strandberg ・ Matroid ・ Matroid embedding ・ Matroid girth ・ Matroid intersection ・ Matroid minor ・ Matroid oracle ・ Matroid partitioning ・ Matroid polytope ・ Matroid rank ・ Matroid representation ・ Matron ・ Matron Head ・ Matron literature ・ Matron Stakes ・ Matron Stakes (Ireland) ・ Matron Stakes (United States) ・ Matron's badge ・ Matrona ・ Matrona (genus) ・ Matrona (Pugad Baboy) ・ Matrona of Barcelona Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Matroid partitioning ： ウィキペディア英語版 Matroid partitioning The matroid partitioning problem is a problem arising in the mathematical study of matroids and in the design and analysis of algorithms, in which the goal is to partition the elements of a matroid into as few independent sets as possible. An example is the problem of computing the arboricity of an undirected graph, the minimum number of forests needed to cover all of its edges. Matroid partitioning may be solved in polynomial time, given an independence oracle for the matroid. It may be generalized to show that a matroid sum is itself a matroid, to provide an algorithm for computing ranks and independent sets in matroid sums, and to compute the largest common independent set in the intersection of two given matroids.〔.〕 ==Example== The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned, or equivalently (by adding overlapping edges to each forest as necessary) the minimum number of spanning forests whose union is the whole graph. A formula proved by Crispin Nash-Williams characterizes the arboricity exactly: it is the maximum, over all subgraphs $H$ of the given graph $G$, of the quantity $\backslash left\backslash lceil\backslash frac\backslash right\backslash rceil$.〔.〕 The forests of a graph form the independent sets of the associated graphic matroid, and the quantity $|V(H)|-1$ appearing in Nash-Williams' formula is the rank of the graphic matroid of $H$, the maximum size of one of its independent sets. Thus, the problem of determining the arboricity of a graph is exactly the matroid partitioning problem for the graphic matroid. The fact that the $|E(H)|$ elements of this matroid cannot be partitioned into fewer than $\backslash frac$ independent subsets is then just an application of the pigeonhole principle saying that, if $x$ items are partitioned into sets of size at most $y$, then at least $x/y$ sets are needed. The harder direction of Nash-Williams' formula, which can be generalized to all matroids, is the proof that a partition of this size always exists.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Matroid partitioning」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.